#ifndef NUMBERTHEORY_H_INCLUDED
#define NUMBERTHEORY_H_INCLUDED

/**
  * Producted by Earthson
  * Email: Earthson.Landy@gmail.com
  * http://www.earthson.net
  **/

extern const int N;
extern int ph[],prime[],pri[],sig[],productorcnt[];

/**
  * GCD
  **/
int gcd(int a,int b);
/**
  * LCM of k numbers
  **/
int lcm(int *table,int k);
/**
  * Extended Euclid's Algorithm
  **/
int extended_gcd(int a,int b,int &x,int &y);
/**
  * a*b mod m ||| you may need this to deal with bigger m in the functions below^^
  * m*2<INT_MAX
  **/
int a_Multiply_b_Mode_m(int a,int b,int m);
/**
  * Successive square method
  * O(lgn)
  **/
int Power_k_Mod_m(int x,int k,int m);  ///x^k(mod m)
int power (int x, int k);
/**
  * Computing k-th Roots Modulo m
  * x^k = b (mod m) ,return x
  * Be sure that gcd(b,m)=1,and gcd(k,phi(m))=1.
  * if gcd(b,m) == gcd(b^2,m),it may have a solution too,
  * in this situation,you need do some convertion^^.
  * but if not ,the solution does not exist.
  **/
int Root_k_Mode_m(int b,int k,int m);
/**
  * 1+q+q^2+...+q^n-1
  * O(logn)
  **/
int sum_Mode_m(int q,int n,int m); ///(1+q+q^2+...+q^n-1) mod m
/**
  * Prime number sieve Method
  * O(n)
  **/
int get_prime();  ///primes frome 1 to N
/**
  * MilleršCRabin primality test
  **/
bool MR_primality_test(int x);
bool isPrime(int x);
/**
  * phi(n) !!!need prime table
  * if the table is N,be sure that n*n<=N
  **/
int phi(int n);
/**
  * phi(n) !!!No prime table
  **/
int phi_2(int n);
/**
  * phi from 1 to N
  **/
void phi_all();
/**
  * sigma(n) ||| need prime table!
  * sum of all productors of n
  **/
int sigma(int n);
/**
  * sigma(n) ||| if you do not have a  prime table^^
  * sum of all productors of n
  **/
int sigma2(int n);
/**
  * sigma(n) ||| if you do not have a  prime table^^
  * sum of all productors of n for all n no more than N^^
  **/
void sigma_all();
/**
  * productors number of all number  frome 1 to N
  * O(n)
  **/
void productor_all();
/**
  * get n! mod m
  * O(n/ln(n))
  * You need a prime table^^
  * if n! = a * m^k,and a mod m != 0
  * then return a mod m,and you can get k from the value over^^
  **/
int factorial_mod_p (int n, int p, int &over);
int factorial_mod_p_liner(int n, int p, int &over);
/**
  * Combinations mod m
  * O(lgb*b^2)
  **/
int combination_Mod_m(int a,int b,int m); ///m*m<INT_MAX
int combination_Mod_p(int n, int m, int p);
int combination_Mod_pk(int n, int m, int p, int k);
int combination_Mod_s(int n, int m, int s);
int combination_Mod_h (int n, int m, int h);
/**
  * small Combinations
  * C(n,m)<LONG_LONG_MAX
  * almost O(m)
  **/
int combination(int n,int m);
/**
  * Linear congruence theorem
  * gcd(m,n)=1,x=b(mod m),x=c(mod n),0<=x<mn
  **/
int linear_congruence_theorem(int b,int c,int m,int n);
/**
  * Polya for Dihedral group(n rotational symmetries and n reflection symmetries)
  * n points and c colors
  **/
int polya(int c,int n);
/**
  * Lucas' theorem---combination number mod prime p
  **/
int lucas(int m,int n,int p);
/**
  * Baby step, Giant step for Discrete Logarithm
  * O(sqrt(n))
  **/
int babyStep_gaintStep(int a, int b, int p);
#endif // NUMBERTHEORY_H_INCLUDED
